1. Technical Field
The invention relates to data processing systems utilizing a virtual storage system and more particularly to page replacement based on assembling blocks of pages for movement between storage and physical memory. The invention relates still more particularly to a system for grouping non-contiguous pages into blocks based on memory reference behavior.
2. Description of the Related Art
In most computers, a single central processing unit periodically executes each of a plurality of current processes. This is called multitasking. Before a data to be used by a task can be loaded into the registers of the central processing unit the data must be resident in physical memory. If too many processes are current, insufficient space will exist in physical memory to load all of each process into physical memory. At some point physical memory is simply exhausted.
Virtual storage provides a way of evading the constraints of physical memory size on program size or on the number of programs which may be current. In a system using virtual storage, addresses in a virtual address space are substituted for addresses in physical memory. Because the address space of virtual storage is much larger than the address space of physical memory, programs which cumulatively exceed physical memory in size may be placed in an executable format by the simple expedient of substituting virtual addresses for real addresses. Depending upon the addressing scheme of the computer and its operating system, the address space of virtual storage can extend over all of the auxiliary storage available to a computer, including disk drives and tape drives. The practical implication of this arrangement is that some of the instructions and the data of a process will not be in physical memory when called, even though they may be assigned system addresses and addressed from a process. These instructions must then be moved from auxiliary storage into physical memory. A virtual storage operating system undertakes movement of data between physical memory and auxiliary storage in a manner transparent to the program. Any conflicts for the space are resolved by the operating system by dropping or paging out data to make room for addressed data.
With increases in the number of current processes, the space available in physical memory to each process decreases and the demand for transfers of data to and from auxiliary storage increases. Addressing auxiliary storage is extremely time consuming relative to addressing physical memory, although once undertaken, it is far more efficient to exchange large quantities of data. Thus, implementation of virtual storage can adversely effect system performance. The computer can reach a point where it spends more time moving data back and forth between physical memory and auxiliary storage then performing useful work, a phenomena called thrashing.
Memory management has as an object the efficient support of multiple concurrent processes on a computer using a virtual storage operating system. Efficient implementation of a virtual storage system has two seemingly incompatible objectives. These objectives are efficient utilization of physical memory (met by keeping only the most frequently used data in physical memory to avoid the need to move data) and efficiency in input/output operations (met by moving as much data as possible between physical memory and auxiliary storage with each input/output operation because any time such an operation is undertaken a great deal of time is lost). The objectives are seemingly incompatible because the first objective calls for fine adjustments and the latter objective demands gross adjustments in the contents of physical memory.
The "Locality of Reference" phenomena affords some possibility of reconciling the two objectives. The locality model of computer programs states that, as a program is executed, processing moves from locality to locality within the program. A locality includes those data and instructions which are accessed, perhaps repeatedly, during a period of time. Ideally, instructions and data that are used together are a locality. A relatively clean locality will typically occur with a subroutine. Memory references will typically be made to the lines of code of the subroutine, the local variables of the subroutine and possibly certain global variables. A program typically exhibits several localities, which may overlap. In many operating systems, a function called the scheduler signals to the memory manager which tasks (objects) are to be used, when they are to be used and what pages are expected to be used with those tasks. The scheduling function is called long term scheduling. The long term scheduler is able to identify localities to the memory manager. Memory management is aided by an interface allowing transfer of the long term scheduling information to memory management.
In UNIX operating systems and derivatives thereof (UNIX is a trademark of America Telephone & Telegraph, Inc.) there is no long term scheduling, only short term priority scheduling. No interface is provided for transfer of information identifying a locality to a memory manager. UNIX operating systems work with finer granularity of its address space than other systems further complicating memory management functions. To add such features to the UNIX operating system is possible, but would erode the simplicity of the UNIX operating system and its derivatives which has made the system commercially successful. It is desirable to provide for page out and page in of blocks of virtual pages on a UNIX or UNIX like operating system without reliance on scheduler information.